// 循环结束时，left 指向的是“第一个大于等于 target 的位置”，这个位置就是插入点
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (target > nums[left]) return left+1; // 如果target大于数组中所有元素，那就要返回left+1
        return left;
    }
}
// 为什么直接 return left
// 因为如果上面的没有返回 return mid，说明最后一定是 left>right 从而跳出循环的
// 在此之前是 left=right，如果最后是 right-1 导致的 left>right，说明原来的 right 位置是大于 target 的，所以返回原来的 right 位置即 left 位置
// 如果最后是 left+1 导致的 left>right，说明是原来的的 left=right 这个位置小于 target，而 right 能移动到这个位置，说明此位置右侧是大于 target 的，left现在加1就移动到了这样的位置，返回 left 即可